home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / ARASAN_S.ZIP / SEARCH.CPP < prev    next >
C/C++ Source or Header  |  1994-08-14  |  37KB  |  1,350 lines
  1. // Copyright 1994 by Jon Dart.  All Rights Reserved.
  2.  
  3. #include "bearing.h"
  4. #include "search.h"
  5. #include "scoring.h"
  6. #include "constant.h"
  7. #include "movegen.h"
  8. #include "moveord.h"
  9. #include "util.h"
  10. #include "rmove.h"
  11. #include "pinfo.h"
  12. #include "attacke.h"
  13. #ifdef WINDOWS
  14. #include "clock.h"
  15. #include "display.h"
  16. #endif
  17. #include "options.h"
  18. #include "globals.h"
  19. #ifdef WINDOWS
  20. #include <wpapp.h>
  21. #define SEARCH_TIMER 2
  22. #else
  23. #include <stdio.h>
  24. #define wsprintf sprintf
  25. #endif
  26. #ifdef TRACE
  27. #include <iostream.h>
  28. #endif
  29. #include <limits.h>
  30.  
  31. #if defined(__BORLANDC__) && !defined(WINDOWS)
  32. // expand default stack size
  33. extern unsigned _stklen = 0x8000;
  34. #endif
  35. extern Options *global_options;
  36.  
  37. // Define the allocators for the hash table here:
  38. Pool S_Node<Position_Info>::allocator(4096);
  39. Pool S_List<Position_Info>::allocator(4096);
  40.  
  41. #ifdef WINDOWS
  42. // We have a limited ability to perform multiple searches at once.
  43. // E.g. the "hint" function uses this.  Each search gets its own
  44. // timer.
  45. #define MAX_SEARCHES 3
  46. static int num_searches = 0;
  47. static Search *searches[MAX_SEARCHES];
  48. HACCEL Search::accel = 0;
  49. #endif
  50.  
  51. static unsigned pred_moves = 0;
  52. static unsigned moves_in_game = 0;
  53.  
  54. const int Illegal = Constants::BIG + 1000;
  55.  
  56. #ifdef TRACE
  57. static void indent(const int ply)
  58. {
  59.    for (int k = 0; k < ply; k++) cout << ' ';
  60. }
  61. #endif
  62.  
  63. #ifdef USE_HASH
  64. // To reduce the chance of a hash collision, we do some elementary
  65. // testing on moves returned by the hash table, to help weed out
  66. // any that are invalid in the current board position ..
  67. static Boolean hash_move_valid( const Board &board, const Move &move)
  68. {
  69.     if (move.IsNull())
  70.         return True;
  71.     Piece p = board[move.StartSquare()];
  72.     if (!p.IsEmpty() && p.Color() == board.Side())
  73.     {
  74.       p = board[move.DestSquare()];
  75.     return (p.IsEmpty() || p.Color() != board.Side());
  76.     }
  77.     else
  78.         return False;
  79. }
  80. #endif
  81.  
  82. struct Extensions
  83. {
  84.     enum { Capture_Depth = 4 };
  85.     enum { Check_Depth = 2 };
  86.     enum { Max_Extension = 4};
  87. };
  88.  
  89. Search::Statistics::Statistics()
  90. {
  91.    clear();
  92. }
  93.  
  94. void Search::Statistics::clear()
  95. {
  96.    state = Normal;
  97.    value = 0;
  98.    for (int i = 0; i < Constants::MaxPly; i++)
  99.        best_line[i].MakeNull();
  100.    elapsed_time = 0;
  101.    plies_completed = max_depth = 0;
  102.    num_moves = num_pos = 0;
  103. }
  104.  
  105. int Search::get_ply() const
  106. {
  107.      return display_depth;
  108. }
  109.  
  110. unsigned long Search::get_numpos() const
  111. {
  112.      return num_pos;
  113. }
  114.  
  115. void Search::terminate_now()
  116. {
  117.     time_up = True; terminated = True;
  118. }
  119.  
  120. #ifdef WINDOWS
  121. void FAR PASCAL _export TimerProc( HWND hWnd, UINT /*msg*/, UINT wParam, 
  122. DWORD /*lParam*/)
  123. {
  124.     // timer callback function
  125.     time_t current_time = time(NULL);
  126.     Search *searcher = searches[wParam-SEARCH_TIMER];
  127.     if (searcher->was_terminated())
  128.         return;
  129.     const Search_Type src_type = searcher->get_search_type();
  130.     if (src_type != Fixed_Ply &&
  131.        current_time - searcher->get_start_time() > searcher->get_time_limit())
  132.        searcher->set_time_up(True);
  133.     the_clock->update( );
  134. //    if (src_type != Fixed_Ply && src_type != Time_Limit)
  135. //    {
  136. //       // check if we've exceeded the time control
  137. //       if (the_clock->time_left(the_clock->get_side_to_move()) == 0)
  138. //          searcher->set_time_up(True);
  139. //    }
  140.     if (!searcher->is_background_search())
  141.     {
  142.        Display::show_search_counts(hWnd,
  143.          searcher->get_ply(),searcher->get_numpos());
  144.     }
  145. }
  146. #endif
  147.  
  148. Boolean Search::
  149. skip_move(const Board & ABoard, const unsigned ply, const unsigned limit,
  150.       const ExtendedMove & emove, const Boolean in_check)
  151. {
  152.     // Returns true if 'emove' is *not* to be evaluated.  This function
  153.     // implements the capture and check extension heuristics.
  154.     int limit2 = limit + extend;
  155.     if (ply < limit2)
  156.     return False;
  157.     else if (ply <= limit2 + Extensions::Check_Depth && in_check)
  158.     return False;
  159.     else if (ply < limit2 + Extensions::Capture_Depth)
  160.     {
  161.     if (emove.Special() == ExtendedMove::Promotion)
  162.     {
  163.         return False;
  164.     } 
  165.     else if (emove.Special() == ExtendedMove::Normal &&
  166.            !emove.Capture().IsEmpty())
  167.     {
  168.         if (Scoring::check_en_prise(ABoard,emove.DestSquare(),
  169.             emove.Capture()))
  170.         return False;
  171.         else if (attack_estimate( ABoard, emove ) >= 0)
  172.             return False;
  173.         else if (emove.PieceMoved().sliding() &&
  174.             !ABoard.pawn_attacks(emove.DestSquare(),
  175.          ABoard.OppositeSide()))
  176.         {
  177.                 // Arasan's attack estimation code does not handle
  178.                 // "stacked" attackers.  To partially compensate for
  179.                 // this, we extend the search when the capturing piece
  180.                 // is "backed up" by a piece of the same color:         
  181.             int dir = ABoard.Direction(emove.StartSquare(),
  182.                 emove.DestSquare());
  183.         if (dir)
  184.         {
  185.             Square sq(emove.StartSquare());
  186.             while (!sq.OnEdge()) 
  187.             {
  188.                sq -= dir;
  189.                Piece p = ABoard[sq];
  190.                if (p.IsEmpty())
  191.                    continue;
  192.                else if (p.Color() != ABoard.Side())
  193.                    break;
  194.                if (p.sliding())
  195.                {
  196.                     Piece::PieceType ptype = p.Type();
  197.                    if (emove.PieceMoved().Type() == Piece::Rook)
  198.                     return ptype == Piece::Bishop;
  199.                else if (emove.PieceMoved().Type() == 
  200.                        Piece::Bishop)
  201.                    return ptype == Piece::Rook;
  202.                    else
  203.                {
  204.                     int abs = Util::Abs(dir);
  205.                 if (abs == 1 || abs == RankIncr)
  206.                     return ptype == Piece::Bishop;
  207.                 else
  208.                     return ptype == Piece::Rook;
  209.                    }
  210.                }
  211.             }
  212.         }
  213.         }
  214.         else
  215.             return True;
  216.     } else
  217.         return True;
  218.     } 
  219.     return True;
  220. }
  221.  
  222. int Search::
  223. try_move(Board & ABoard, const ExtendedMove & emove,
  224.      const int ply, int alpha, int &beta, const int rank,
  225.      const Boolean princip_var, const Boolean extend_search,
  226.      Boolean &terminate, Move *best_line)
  227. {
  228. #ifdef TRACE
  229.     if (ply == 0)
  230.        cout << "window = [" << alpha << ',' << beta << ']' << endl;
  231.     indent(ply);
  232.     cout << "trying " << ply << ". " << emove.Image() << endl;
  233. #endif
  234.  
  235. #ifndef NULL_MOVE
  236.     assert(!emove.IsNull());
  237. #endif
  238.     // search one ply deeper, following 'emove'.  If 'extend_search'
  239.     // is set, search two plies.
  240.  
  241.     int score;
  242.     // allocate on the heap (to minimize stack usage):
  243.     if (move_stack[ply] == NULL)
  244.       move_stack[ply] = new ReversibleMove(ABoard, emove);
  245.     else
  246.       *(move_stack[ply]) = ReversibleMove(ABoard, emove);
  247.     ABoard.MakeMove(*(move_stack[ply]));
  248.     game_moves->add_move(ABoard,*(move_stack[ply]));
  249.     if (ABoard.num_attacks(ABoard.KingPos(ABoard.OppositeSide()),
  250.                ABoard.Side()) > 0)  // move into check
  251.     {
  252. #ifdef TRACE
  253.         indent(ply);
  254.     cout << "(illegal)" << endl;
  255. #endif
  256.     score = Illegal;
  257.     }
  258.     else
  259.     {
  260.     last_move[ply] = emove;
  261.     if (princip_var || rank == 1)
  262.     {
  263.        if (extend_search)
  264.        {
  265.           extend++;
  266.           score = -move_search(ABoard, -beta, -alpha, ply + 1, 
  267.                       princip_var,
  268.                   terminate, best_line);
  269.           extend--;
  270.        }
  271.        else
  272.           score = -move_search(ABoard, -beta, -alpha, ply + 1, 
  273.                   princip_var,
  274.                   terminate, best_line);
  275. #ifdef TRACE
  276.       indent(ply);
  277.       cout << ply << ". " << emove.Image() << ' ';
  278.        cout << score;
  279.       if (princip_var)
  280.          cout << " (pv)";
  281.       cout << endl;
  282. #endif
  283.     }
  284.     else
  285.     {
  286.        if (extend_search)
  287.        {
  288.            ++extend;
  289.         score = -move_search(ABoard, -alpha-1, -alpha, ply + 1,
  290.             princip_var,
  291.                terminate, best_line);
  292.         --extend;
  293.        }
  294.        else
  295.         score = -move_search(ABoard, -alpha-1, -alpha, ply + 1,
  296.             princip_var,
  297.                terminate, best_line);
  298. #ifdef TRACE
  299.        indent(ply);
  300.        cout << ply << ". " << emove.Image() << ' '; 
  301.         cout << score << endl;
  302. #endif
  303.        if (!emove.IsNull() && score > alpha && score < beta)
  304.        {
  305. #ifdef TRACE
  306.           indent(ply);
  307.           cout << "no cutoff, re-searching..." << endl;
  308. #ifdef TRACE
  309.     if (ply == 0)
  310.        cout << "window = [" << -beta << ',' << -score << ']' << endl;
  311.     indent(ply);
  312.     cout << "trying " << ply << ". " << emove.Image() << endl;
  313. #endif
  314. #endif
  315.           if (extend_search)
  316.           {
  317.               extend++;
  318.               score = -move_search(ABoard, -beta, -score, ply + 1,
  319.                   princip_var,
  320.                   terminate, best_line);
  321.           extend--;
  322.           }
  323.           else
  324.                   score = -move_search(ABoard, -beta, -score, ply + 1,
  325.                   princip_var,
  326.                   terminate, best_line);
  327. #ifdef TRACE
  328.          indent(ply);
  329.          cout << ply << ". " << emove.Image() << ' ';
  330.           cout << score << endl;
  331. #endif
  332.        }
  333.     }
  334.     }
  335.     ABoard.UndoMove(*(move_stack[ply]));
  336.     game_moves->remove_move();
  337. #ifdef WINDOWS
  338.     // Yield control via PeekMessage to allow other Windows applications
  339.     // to run when our message queue is empty.  Also, this allows
  340.     // keyboard accelerators to be active during a background search.
  341.     if (!accel)
  342.         accel = App.loadAccel("AppAccel");
  343.     HWND hwnd = (*appWin)();
  344.     MSG msg;
  345.     if (!terminated && PeekMessage(&msg,NULL,0,0,PM_REMOVE))
  346.     {
  347.       if (msg.message==WM_QUIT ||
  348.           msg.message==WM_DESTROY || 
  349.           (msg.message==WM_SYSCOMMAND && msg.wParam == SC_CLOSE))
  350.       {
  351.           // We cannot handle WM_QUIT during a search in the usual
  352.           // way.  We need to map it into WM_CLOSE.
  353.           terminated = True;
  354.           // make sure our search won't be interrupted:
  355.           KillTimer(my_hwnd,idTimer);
  356.           PostMessage(hwnd,WM_CLOSE,0,0L);
  357.       }
  358.           else if (!(accel && TranslateAccelerator(hwnd, accel, &msg)))
  359.       {
  360.                TranslateMessage(&msg);
  361.          DispatchMessage(&msg);
  362.       }
  363.     }
  364. #else
  365.     // Provide a simple polling method of terminating after a set time
  366.     time_t current_time = time(NULL);
  367.     if (get_search_type() != Fixed_Ply &&
  368.         current_time - get_start_time() > time_target)
  369.        set_time_up(True);
  370. #endif
  371.     if (terminated)
  372.     {
  373.         time_up = True;
  374.     terminate = True;
  375.     }
  376.     const Search_Type type_of_search = get_search_type();    
  377.     if (type_of_search != Fixed_Ply && 
  378.         type_of_search != Time_Limit)
  379.     {
  380.        // Allow terminating early if the pv move appears to be
  381.        // clearly superior to all others and was in the last ply, too:
  382.        if (!time_up && ply == 0 && rank > 1 && plies_done >= 3)
  383.        {
  384. #ifdef WINDOWS
  385.        // require that we have consumed at least 1/3 of the time
  386.        // limit:
  387.            time_t current_time = time(NULL);
  388.            if ((current_time - get_start_time())*3 > time_target)
  389.        {
  390. #endif
  391.        if (ply0scores[0] > ply0scores[1] + 128 &&
  392.                ply0moves[0] == best_moves[plies_done] &&
  393.            ply0scores[0] >= best_scores[plies_done] - 32)
  394.           time_up = True;
  395. #ifdef WINDOWS
  396.        }
  397. #endif
  398.        else if (!time_added && ply == 0 && plies_done >= 3 && 
  399.                 rank > 0)
  400.        {
  401.            time_t current_time = time(NULL);
  402.                if ((current_time - get_start_time())*3 > 2*time_target)
  403.            {
  404.               // add a little more time to the search if the score
  405.               // has changed a lot since the last ply.
  406.               if (Util::Abs(ply0scores[0]-best_scores[plies_done]) > 64)
  407.               {
  408.                   time_added = time_target/4;
  409.               time_up = False;
  410.           }
  411.            }
  412.        }
  413.        }
  414.     }
  415.     if (time_up)
  416.     {
  417.         terminate = True;
  418.         if (!princip_var) // don't allow current move to be selected
  419.              score = Illegal;
  420.     }
  421.     return score;
  422. }
  423.  
  424. unsigned Search::
  425. generate_moves(
  426.            Board & board, Move_Generator & mg,
  427.            const unsigned ply,
  428.            Move * moves,
  429.            const Boolean captures_only)
  430. {
  431.     int i;
  432.     if (ply == 0 && ply0moves_generated)
  433.     {
  434.         // Make sure that in case of a tied score, the actually
  435.     // chosen best move at ply n-1 is used first in this ply:
  436.         for (i = 0; i < ply0move_count; i++)
  437.        if (pv[0] == ply0moves[i])
  438.        {
  439.           ply0scores[i]++;
  440.           break;
  441.        }
  442.     Move_Ordering::sort_moves(ply0moves, ply0scores, ply0move_count);
  443.     // Because of cutoffs, we may not have exact scores for
  444.     // moves besides the p.v.  Therefore still use the move ordering
  445.     // code to tweak the remaining scores a bit.
  446.     if (ply0move_count > 1)
  447.     {
  448.       for (i = 1; i < ply0move_count; i++)
  449.          ply0scores[i] += Move_Ordering::score(board,ply0moves[i]);
  450.       Move_Ordering::sort_moves(ply0moves+1, ply0scores+1, ply0move_count-1);
  451.     }
  452.     for (i = 0; i < ply0move_count; i++)
  453.         moves[i] = ply0moves[i];
  454.     return ply0move_count;
  455.     }
  456.     int    n = mg.Generate_Moves(moves, captures_only);
  457.  
  458.     Move_Ordering::order_moves(board, moves, n, ply, Move::NullMove());
  459.     return n;
  460. }
  461.  
  462. int Search::
  463. evalu8(const Board & board)
  464. {
  465.     // evaluate a board position.
  466.     num_pos++;
  467.     int score = Scoring::material_score(board);
  468.     score += Scoring::positional_score(board);
  469.     if (global_options->randomize_moves())
  470.     {
  471.         static int fudge = Constants::PawnValue/10;
  472.     int r = rand()/16;
  473. #ifdef __BORLANDC__
  474.     score += -fudge + (r*fudge)/(RAND_MAX/16);
  475. #else
  476.     score += -fudge + (r*fudge)/(INT_MAX/16);
  477. #endif
  478.     }
  479.     return score;
  480. }
  481.  
  482. Boolean Search::is_draw( const Board &board, int &rep_count)
  483. {
  484.     // check for draws due to repetition or insufficient material.
  485.  
  486.     rep_count = game_moves->rep_count(board);
  487.     if (rep_count >= 3)
  488.       return True;
  489.     // check for insufficient material
  490.     const Material &mat1 = board.getMaterial(board.Side());
  491.     const Material &mat2 = board.getMaterial(board.OppositeSide());
  492.     unsigned pcount1 = mat1.count(Piece::Pawn);
  493.     unsigned pcount2 = mat2.count(Piece::Pawn);
  494.     if (pcount1 || pcount2)
  495.        return False;
  496.     const int16 king_value = Piece::Value(Piece::King);
  497.     const int16 bishop_value = Piece::Value(Piece::Bishop);
  498.     if ((mat1.value() <= king_value + bishop_value) &&
  499.     (mat2.value() <= king_value + bishop_value))
  500.     {
  501.         if (mat1.king_only() || mat2.king_only())
  502.     // K vs K, or K vs KN, or K vs KB
  503.        return True;
  504.         else if (mat1.count(Piece::Knight) || mat2.count(Piece::Knight))
  505.         {
  506.        // KN vs KN 
  507.        return False;
  508.     }
  509.         else
  510.     {
  511.        int i = 0;
  512.            int d1 = -1;
  513.        int d2 = -1;
  514.        do
  515.        {
  516.           Square sq(board.PiecePos(board.Side(),i));
  517.           if (!sq.IsInvalid())
  518.           {
  519.              Piece::PieceType piece = board[sq].Type();
  520.              if (piece == Piece::Bishop)
  521.              {
  522.                 d1 = (sq.Rank(board.Side()) + sq.File()) % 2;
  523.              }
  524.              sq = board.PiecePos(board.OppositeSide(),i);
  525.          if (!sq.IsInvalid())
  526.          {
  527.                 piece = board[sq].Type();
  528.                 if (piece == Piece::Bishop)
  529.                 { 
  530.                     d2 = (sq.Rank(board.Side()) + sq.File()) % 2;
  531.                 }
  532.                  }
  533.           }
  534.           i++;
  535.            } while (i < 16);
  536.        // drawn if same-color bishops:
  537.        return Boolean(d1 == d2);
  538.         }
  539.     }
  540.     return False;
  541. }
  542.  
  543. int Search::
  544. move_search(Board & ABoard, int alpha, int beta,
  545.         const int ply, const Boolean princip_var,
  546.         Boolean &terminate, Move *best_line)
  547. {
  548.     // recursive function, implements alpha/beta search.  We use
  549.     // the PVS (principal variation search) variant of alpha/beta.
  550.  
  551.     unsigned num_try = 0;
  552.     int score;
  553.     struct flag_struct
  554.     {
  555.        int in_check;
  556.        int mate;
  557.        int capture_search;
  558.        int finished;
  559.        int forced;
  560.     } flags;
  561.     flags.in_check =  ABoard.CheckStatus() == Board::InCheck;
  562.     flags.mate = flags.capture_search = flags.finished = 
  563.       flags.forced = False;
  564. #ifdef USE_HASH
  565.     const int initial_alpha = alpha;
  566. #endif
  567.     forced[ply] = False;
  568.     int limit = max_depth;
  569.     for (int p = ply-1; p>=0; --p)
  570.        if (forced[p]) ++limit;
  571.     if (ply == 0)
  572.        rank = 0;
  573.     int rep_count;
  574.  
  575.     if (is_draw(ABoard,rep_count))
  576.     {
  577. #ifdef TRACE
  578.     cout << "draw!" << endl;
  579. #endif
  580.        if (ply == 0)
  581.           state = Search::Draw;
  582.        return -evalu8(ABoard);
  583.     }
  584.     else if (ply >= max_depth + Extensions::Max_Extension + extend
  585.        || ply >= Constants::MaxPly)
  586.     {
  587.     return evalu8(ABoard);
  588.     }
  589.  
  590.     Move hash_move;
  591. #ifdef USE_HASH
  592.     if (ply > 0 && ply <= max_depth 
  593. #ifdef NULL_MOVE
  594.     && !null_move)
  595. #else
  596.     )
  597. #endif
  598.     {
  599.         Position_Info *hash_entry;    
  600.     Position_Info look(ABoard,rep_count);
  601.         hash_entry = hash_table->search(look);
  602.     if (hash_entry)
  603.     {
  604.        hash_move = hash_entry->best_move();
  605.        if (!hash_move_valid(ABoard,hash_move))
  606.        {
  607.           hash_entry = NULL;
  608.           hash_move.MakeNull();
  609.        }
  610.     }
  611.     if (hash_entry)
  612.         {
  613.         flags.forced = forced[ply] = hash_entry->forced();
  614.         if (hash_entry->depth() >= limit-ply)
  615.         {
  616.         // Whether we can use the hash value or not depends on
  617.         // the flags:
  618.         const int value = hash_entry->value();
  619.         Boolean valid = False;
  620.         switch(hash_entry->type())
  621.         {
  622.            case Position_Info::Valid:
  623.              valid = True;
  624.          break;
  625.            case Position_Info::UpperBound:
  626.          beta = Util::Min(value,beta);
  627.          break;
  628.            case Position_Info::LowerBound:
  629.          alpha = Util::Max(value,alpha);
  630.          break;
  631.            default:
  632.              break;
  633.         }
  634.             best_line[ply] = hash_entry->best_move();
  635.         best_line[ply+1] = Move::NullMove();
  636.         if (valid)
  637.         {
  638.            return hash_entry->value();
  639.         }
  640.         else if (alpha > beta)
  641.         {
  642.            if (hash_entry->type() == Position_Info::LowerBound)
  643.                return alpha;
  644.            else
  645.                return beta;
  646.         }
  647.         }
  648.     }
  649.     }
  650. #endif
  651.  
  652. #ifdef TRACE
  653.    if (!hash_move.IsNull())
  654.    {
  655.           indent(ply);
  656.        cout << "hash move = " << hash_move.Image() << endl;
  657.    }
  658. #endif
  659.  
  660.     score = -Constants::BIG;
  661.     Move *moves = moves_generated[ply];
  662.     Move *candidate_line = candidates[ply];
  663.     if (!candidate_line)
  664.     {
  665.        candidate_line = candidates[ply] = new Move[Constants::MaxPly];
  666.     }
  667.     int try_score;
  668.     ExtendedMove the_last_move;
  669.     Move best_move;
  670.  
  671.     if (ply != 0)
  672.     the_last_move = last_move[ply - 1];
  673.  
  674.     // Most extensions do not alter the onset of the quiescence search,
  675.     // just its termination depth.  However, forced moves do extend the
  676.     // start of the quiesence search, to 'limit'.  We do this for two
  677.     // reasons: it is relatively cheap, and it helps find (or avoid)
  678.     // forced mating sequences.
  679.     flags.capture_search = (ply >= limit && !flags.in_check);
  680.     int cap_score = -Constants::BIG;
  681.     Boolean extend_search = False;
  682.  
  683.     if (flags.capture_search)
  684.     {
  685.     // We are in the capture search and will not consider
  686.     // all possible moves (or even all possible captures).
  687.     // Hence, we evaluate the present position and use the more
  688.     // optimistic of the value of the present position and the
  689.     // best value returned by the capture search.  
  690.  
  691.     // But we do not allow the side to move to "stand pat" if it
  692.     // has a trapped or hung piece.
  693.  
  694.     int value = evalu8(ABoard);
  695.     if ((Scoring::trapped || (Scoring::en_prise >= 1)) &&
  696.         ply == limit /*max_depth*/)
  697.     {
  698.         extend_search = True;
  699.         flags.capture_search = False;
  700.     }
  701.     else
  702.     {
  703.             cap_score = score = value;
  704. #ifdef TRACE
  705.             indent(ply);
  706.         cout << "cap_score = " << cap_score << endl;
  707. #endif
  708.     }
  709.     }
  710.  
  711. #ifdef NULL_MOVE
  712.     // Try the null move
  713.     if (!princip_var && !flags.in_check && !null_move && 
  714.         ply <= limit - 3 && 
  715.     ABoard.getMaterial(ABoard.Side()).value() > 2500 &&
  716.     ABoard.getMaterial(ABoard.OppositeSide()).value() > 2500)
  717.     {
  718.         null_move = True;
  719.     // search to less than full depth:
  720.     --max_depth;
  721.     ExtendedMove emove; // null move
  722.         try_score = try_move(ABoard, emove, ply, alpha, beta, num_try,
  723.                      False, 
  724.                  False,
  725.                  terminate, 
  726.                  candidate_line );
  727.         ++max_depth;                 
  728.         null_move = False;                 
  729.         if (try_score >= beta)
  730.        score = try_score;
  731.     }
  732. #endif
  733.  
  734.     Boolean generated_moves = False;
  735.     unsigned move_count;
  736.     Move_Generator mg(ABoard, ply, the_last_move);
  737.     if (score < beta)
  738.     {
  739.         if (!moves)
  740.            moves = moves_generated[ply] = new Move[Move_Generator::MaxMoves];
  741.         if (hash_move.IsNull())
  742.         {
  743.            move_count = generate_moves(ABoard, mg, ply,
  744.                  moves, 
  745.                  Boolean(flags.capture_search));
  746.            num_moves += move_count;
  747.            generated_moves = True;
  748.        flags.forced = forced[ply] = 
  749.           !flags.capture_search && move_count == 1;
  750.         }
  751.         else
  752.         {
  753.        // Delay generating the moves, use the hash move 1st.
  754.        // If it causes cutoff, we never need to do full move generation.
  755.            move_count = 1;
  756.            moves[0] = hash_move;
  757.         }
  758.     }
  759.  
  760.     // do the principal variation first
  761.  
  762.     candidate_line[ply+1] = Move::NullMove();
  763.     unsigned move_index = 0;
  764.     extend_search = extend_search || flags.forced;
  765.     while (move_index < move_count && score < beta && !flags.mate &&
  766.            !terminate)
  767.     {
  768.     ExtendedMove emove(ABoard, moves[move_index++]);
  769.  
  770.     if (extend_search || 
  771.         !skip_move(ABoard, ply, limit, emove, (Boolean)flags.in_check))
  772.     {
  773.         try_score = try_move(ABoard, emove, ply, alpha, beta, num_try,
  774.                      princip_var,
  775.                  extend_search,
  776.                  terminate, 
  777.                  candidate_line );
  778.         if (try_score != Illegal)
  779.         {
  780.             score = try_score;
  781.         num_try++;
  782.         if (ply == 0)
  783.         {
  784.             ply0moves[0] = emove;
  785.             ply0scores[0] = score;
  786.             rank++;
  787.         }
  788.         best_move = emove;
  789.         if (score < cap_score)
  790.             score = cap_score;
  791.         best_line[ply] = best_move;
  792.         if (ply == 0)
  793.            flags.mate = score >= Constants::BIG - (int)limit - 1;
  794.         else
  795.            flags.mate = score >= Constants::BIG - (int)ply - 1;
  796.         break;
  797.         }
  798.     }
  799. #ifdef TRACE
  800.     else
  801.     {
  802.         indent(ply);
  803.         cout << "skipping " << emove.Image() << endl;
  804.         }
  805. #endif
  806.     }
  807.  
  808.     // Principal variation done, now do the rest of the moves
  809.  
  810.     if (!generated_moves && score < beta && !flags.mate)
  811.     {
  812.        move_count = generate_moves(ABoard, mg, ply,
  813.                  moves, 
  814.                  Boolean(flags.capture_search));
  815.        num_moves += move_count;
  816.        flags.forced = forced[ply] = !flags.capture_search && move_count == 1;
  817.        move_index = 0;
  818.        extend_search = extend_search || flags.forced;
  819.     }
  820.     while (move_index < move_count && score < beta && !flags.mate &&
  821.            !terminate)
  822.     {
  823.         if (num_try > 1)
  824.          alpha = Util::Max(alpha, score);
  825.     ExtendedMove emove(ABoard, moves[move_index++]);
  826.     if (((Move)emove != hash_move) && (extend_search ||
  827.        !skip_move(ABoard, ply, limit, emove, flags.in_check)))
  828.     {
  829.         candidate_line[ply+1].MakeNull();
  830.         try_score = try_move(ABoard, emove, ply,
  831.                   alpha, beta, num_try, False,
  832.                   extend_search, terminate, 
  833.                   candidate_line);
  834.         if (try_score == Illegal || terminate)
  835.         continue;
  836.         else
  837.         num_try++;
  838.         if (try_score < cap_score)
  839.         try_score = cap_score;
  840.         if (try_score > score)   // new best move
  841.         {
  842.         score = try_score;
  843.         best_move = emove;
  844.         int j;
  845.         for (j = ply + 1;
  846.              j < Constants::MaxPly && !candidate_line[j].IsNull();
  847.              ++j)
  848.         {
  849.              best_line[j] = candidate_line[j];
  850.         }
  851.         best_line[j].MakeNull();
  852.         best_line[ply] = best_move;
  853.         if (ply == 0)
  854.            flags.mate = score >= Constants::BIG - (int)limit - 1;
  855.         else
  856.            flags.mate = score >= Constants::BIG - (int)ply - 1;
  857.         }
  858.         if (ply == 0)
  859.         {
  860.         ply0moves[rank] = (Move) emove;
  861.         ply0scores[rank] = try_score;
  862.         rank++;
  863.         }
  864.     }
  865.     }
  866.     flags.finished = move_index == move_count;
  867.     Boolean Cutoff = (score >= beta);
  868. #ifdef TRACE
  869.     if (Cutoff)
  870.     {
  871.        indent(ply);
  872.        cout << "**CUTOFF**" << endl;
  873.     }
  874. #endif
  875.  
  876.     if (num_try == 0 && flags.finished && !flags.capture_search)
  877.     {
  878.     // no moves were tried
  879.     if (flags.in_check)
  880.     {
  881.         if (move_count == 0)    // mate
  882.         {
  883.            score = -(Constants::BIG - ply);
  884.            if (ply == 0)
  885.                state = Search::Checkmate;
  886.         }
  887.         else
  888.         {
  889.             // We generated some moves, and some were legal,
  890.         // but we skipped them all.
  891.         score = evalu8(ABoard);
  892.         }
  893.     }
  894.     else if (ply < limit)    // stalemate
  895.     {
  896.         if (ply == 0)
  897.            state = Search::Stalemate;
  898.         score = -evalu8(ABoard);
  899.     }
  900.     } 
  901.     else if (num_try > 0)
  902.     {
  903.     if (Cutoff)
  904.     {
  905.            // If the last move caused cutoff, and was not an immediate
  906.        // re-capture, save it as a "killer" move:
  907.        if (ply == 0 ||
  908.              last_move[ply].DestSquare() != last_move[ply - 1].DestSquare())
  909.            Move_Ordering::set_killer(last_move[ply], ply);
  910.     }
  911.         // If there's only one legal move, don't search any more:        
  912.         if (ply == 0 && num_try == 1 && flags.finished)
  913.            terminate = True;
  914.     }
  915.     if (terminated) 
  916.     {
  917.            state = Search::Terminated;
  918.     }
  919. #ifdef USE_HASH
  920.     if (ply > 0 && ply <= limit)
  921.     {
  922.         // store the position in the hash table, if there's room
  923.     Position_Info::ValueType val_type;
  924.     if (score <= initial_alpha)
  925.     {
  926.         val_type = Position_Info::UpperBound;
  927. #ifdef TRACE
  928.         cout << 'U';
  929. #endif
  930.         best_move.MakeNull();
  931.     }
  932.     else if (score >= beta)
  933.     {
  934.         val_type = Position_Info::LowerBound;
  935. #ifdef TRACE
  936.         cout << 'L';
  937. #endif
  938.         }
  939.     else
  940.     {
  941.         val_type = Position_Info::Valid;
  942. #ifdef TRACE
  943.         cout << 'E';
  944. #endif
  945.     }
  946.         Position_Info my_pi(ABoard, limit-ply,
  947.        val_type, flags.forced, rep_count, score, best_move);
  948.         Position_Info look(ABoard,rep_count);
  949.         Position_Info *hash_entry = hash_table->search(look);
  950.     if (hash_entry)
  951.     {
  952.        if (limit-ply > hash_entry->depth() || 
  953.            (hash_entry->type() != Position_Info::Valid &&
  954.             val_type == Position_Info::Valid))
  955.           *hash_entry = my_pi;
  956.     }
  957.     else
  958.     {
  959.        hash_table->insert(my_pi);
  960.     }
  961.     }
  962. #endif
  963.     if (ply == 0 && flags.finished)
  964.     {
  965.     ply0move_count = rank;
  966.     ply0moves_generated = True;
  967.     }
  968.     return score;
  969. }
  970.  
  971. Search :: Search()
  972. {
  973.     last_move = new ExtendedMove[Constants::MaxPly];
  974.     best_moves = new Move[Constants::MaxPly];
  975.     pv = new Move[Constants::MaxPly];
  976.     searching = False;
  977.     plies_done = 0;
  978. #ifdef USE_HASH
  979. #ifdef WINDOWS
  980.     // Size the hash table according to how much memory we have.
  981.     // Hash table sizes should be prime.
  982.     static unsigned sizes[8]={ 997, 1997, 3001, 4003, 4999, 6007, 6997, 8003 };
  983.     DWORD memSize = GlobalCompact(0);
  984.     int i;
  985.     for (i = 0; i < 7; i++)
  986.     if (16L*sizeof(Position_Info)*((long)sizes[i]) > memSize/8)
  987.         break;
  988.     hash_table = new Hash < Position_Info > (sizes[i],(unsigned long)(sizes[i])*16L);
  989. #else
  990.     hash_table = new Hash < Position_Info > (Constants::Hash_Size,
  991.                      Constants::Max_Hash_Table_Entries);
  992. #endif
  993. #endif
  994. }
  995.  
  996. Search::~Search()
  997. {
  998.     delete [] last_move;
  999.     delete [] best_moves;
  1000.     delete [] pv;
  1001. #ifdef USE_HASH
  1002.     // free the memory only if this is the only active search:
  1003. #ifdef WINDOWS
  1004.     if (search_number == 0)
  1005. #endif
  1006.     {
  1007.        hash_table->clear(True);
  1008.     }
  1009.     delete hash_table;
  1010. #endif
  1011. }
  1012.  
  1013. Move Search::find_best_move(
  1014. #ifdef WINDOWS
  1015.    HWND hWnd,
  1016. #endif
  1017.    const Board & ABoard,
  1018.    const Time_Info &ti,
  1019. #ifdef WINDOWS
  1020.    const Boolean background,
  1021. #endif
  1022.    Statistics & stats,
  1023.    Move &prev_move,
  1024.    Boolean use_previous_search )
  1025. {
  1026.     searching = True;
  1027.     timeCtrl = ti;
  1028. #ifdef WINDOWS
  1029.     my_hwnd = hWnd;
  1030.     moves_in_game = game_moves->num_moves()/2; // full moves, not half-moves
  1031.     pred_moves = 60;
  1032.     if (moves_in_game > 40)
  1033.        pred_moves += (moves_in_game-40)/2;
  1034. #endif
  1035.     time_added = 0L;
  1036.     const Search_Limit limits = timeCtrl.get_search_limit();
  1037.     switch (timeCtrl.get_search_type())
  1038.     {
  1039.        case Fixed_Ply:
  1040.          break;
  1041.        case Time_Limit:
  1042.          time_target = limits.seconds; 
  1043.      break;
  1044. #ifdef WINDOWS
  1045.        case Tournament:
  1046.      time_target = 
  1047.        (limits.limit.minutes*60L*8L)/(limits.limit.moves*10L);
  1048.           break;
  1049.        case Game:
  1050.      unsigned long game_elapsed = 
  1051.         the_clock->elapsed_time(ABoard.Side());
  1052.          time_target = (limits.limit.minutes*60L - game_elapsed)/
  1053.                 (pred_moves - moves_in_game);
  1054. #else
  1055.       // Tournament & Game limits not supported under DOS
  1056.       default:
  1057.          break;
  1058. #endif
  1059.     }
  1060.     num_pos = num_moves = 0L;
  1061. #ifdef NULL_MOVE
  1062.     null_move = False;
  1063. #endif
  1064.     time_up = terminated = False;
  1065.     side_to_move = ABoard.Side();
  1066. #ifdef WINDOWS
  1067.     bkgrnd_search = background;
  1068.     assert(num_searches < MAX_SEARCHES);
  1069.     search_number = num_searches;
  1070.     searches[search_number] = this;
  1071.     ++num_searches;
  1072. #endif
  1073.     // We can use the results of a previous search only if it
  1074.     // was deep enough and if we predicted the last move.
  1075.     use_previous_search &= (stats.plies_completed >= 2) &&
  1076.        (stats.best_line[0] == prev_move);
  1077.     if (use_previous_search)
  1078.        plies_done = stats.plies_completed - 1;
  1079.     else
  1080.        plies_done = 0;
  1081.     time_t end_time;
  1082.     start_time = time(NULL);
  1083.     state = Search::Normal;
  1084.     extend = 0;
  1085.     int i;
  1086.     Boolean end_of_line = False;
  1087.     for (i = 0; i < Constants::MaxPly; i++)
  1088.     {
  1089.     move_stack[i] = NULL;
  1090.     moves_generated[i] = NULL;
  1091.     candidates[i] = NULL;
  1092.     if (use_previous_search && !end_of_line)
  1093.     {
  1094.        pv[i] = stats.best_line[i+1];
  1095.        end_of_line = pv[i].IsNull();
  1096.     }
  1097.     else
  1098.            pv[i].MakeNull();
  1099.     }
  1100.     if (use_previous_search)
  1101.     {
  1102.        for (int j = 0; j < Constants::MaxPly-1; j++)
  1103.        {
  1104.           ExtendedMove emove;
  1105.           Move_Ordering::get_killer(emove,j+1);
  1106.       Move_Ordering::set_killer(emove,j);
  1107.        }
  1108.     }
  1109.     else
  1110.     {
  1111.        Move_Ordering::clear_killer();
  1112.     }
  1113.     ply0moves_generated = False;
  1114.     ply0move_count = 0;
  1115.  
  1116.     Boolean terminate = False;
  1117.     unsigned ply_limit = (get_search_type() == Fixed_Ply) ? limits.max_ply :
  1118.                   Constants::MaxPly;
  1119. #ifdef WINDOWS
  1120.     // set timer every 1000 ms. (1 second).  Note: we use smart
  1121.     // callbacks (-WS), so we don't need to call MakeProcInstance.
  1122.     idTimer = SetTimer(hWnd, num_searches+SEARCH_TIMER-1, 
  1123.                 1000, (TIMERPROC)TimerProc);
  1124.     if (!idTimer)
  1125.     {
  1126.         MessageBox(hWnd,"Too many clocks or timers!","",
  1127.         MB_ICONEXCLAMATION | MB_OK);
  1128.         ExtendedMove null_move;    
  1129.     return null_move;
  1130.     }
  1131. #endif
  1132.  
  1133.     int start = Util::Max(1,plies_done);
  1134.     // Searching may alter the board, either permanently (e.g. PiecePos)
  1135.     // or temporarily (during a search), so operate on a copy:
  1136.     Board board_copy = ABoard;
  1137.     for (int ply = start;
  1138.          ply <= ply_limit && !terminate && !time_up; 
  1139.      ply++)
  1140.     {
  1141.         plies_done = ply - 1;
  1142.     int value;
  1143.     max_depth = display_depth = ply;
  1144.     int lo_window, hi_window;
  1145.     if (ply == start)
  1146.         value = evalu8(ABoard);
  1147.     else
  1148.         value = stats.value;
  1149.         lo_window = value - Constants::Initial_Search_Window / 2;
  1150.     hi_window = value + Constants::Initial_Search_Window / 2;
  1151.     stats.value =
  1152.       move_search(board_copy, lo_window, hi_window, 0, True,
  1153.               terminate, pv);
  1154.  
  1155.         if (!terminate)
  1156.         {
  1157.        if (stats.value > hi_window)
  1158.        {
  1159. #ifdef TRACE
  1160.           cout << "high cutoff, re-searching ..." << endl;
  1161. #endif
  1162.              // high cutoff, must re-search
  1163.               stats.value =
  1164.              move_search(board_copy, hi_window, Constants::BIG-1, 0, True,
  1165.                       terminate, pv);
  1166.            }
  1167.            else if (stats.value < lo_window )
  1168.        {
  1169. #ifdef TRACE
  1170.              cout << "low cutoff, re-searching ..." << endl;
  1171. #endif
  1172.            stats.value =
  1173.              move_search(board_copy, -Constants::BIG, lo_window, 0, True,
  1174.                       terminate, pv);
  1175.        }
  1176.         }
  1177.  
  1178.         best_moves[ply] = pv[0];
  1179.         best_scores[ply] = stats.value;
  1180. #ifdef TRACE
  1181.     cout << ply << " ply search result: " << pv[0].Image() << 
  1182.        "   value = " << stats.value << endl;
  1183. #endif
  1184.     if (stats.value <= ply - Constants::BIG /* we're checkmated */ ||
  1185.         stats.value > Constants::BIG - 100)    // mate
  1186.         break;
  1187.     }
  1188. #ifdef WINDOWS
  1189.     if (!is_background_search())
  1190.         Display::show_search_counts(hWnd,max_depth,num_pos);
  1191. #endif
  1192.     for (i = 0; i < Constants::MaxPly; i++)
  1193.     {
  1194.     delete move_stack[i];
  1195.     if (moves_generated[i])
  1196.        delete [] moves_generated[i];
  1197.     if (candidates[i])
  1198.        delete [] candidates[i];
  1199.     }
  1200.     Move ret_val = pv[0];
  1201. #ifdef WINDOWS
  1202.     KillTimer(hWnd,idTimer);
  1203. #endif
  1204.  
  1205.     end_time = time(NULL);
  1206.     stats.elapsed_time = end_time - start_time;
  1207.     stats.num_pos = num_pos;
  1208.     stats.num_moves = num_moves;
  1209.     stats.state = state;
  1210.     stats.max_depth = display_depth;
  1211.     if (!terminated && get_search_type() == Fixed_Ply)
  1212.        ++plies_done;
  1213.     stats.plies_completed = plies_done;
  1214.     board_copy = ABoard;
  1215.     int p;
  1216.     Move best = pv[0];
  1217.     Move_Array tmpArray;
  1218.     // Try to obtain the best line from the hash table
  1219. #ifdef USE_HASH
  1220.     for (p = 0; p < Constants::MaxPly-1; ++p)
  1221.     {
  1222.         stats.best_line[p] = best;
  1223.     ExtendedMove emove(board_copy,best);
  1224.         board_copy.MakeMove(emove);
  1225.     tmpArray.add_move(board_copy,emove);
  1226.     Position_Info look(board_copy,tmpArray.rep_count(board_copy));
  1227.         Position_Info *hash_entry = hash_table->search(look);
  1228.     if (hash_entry)
  1229.     {
  1230.         best = hash_entry->best_move();
  1231.         if (!hash_move_valid(board_copy,best))
  1232.            break;
  1233.         }
  1234.     else
  1235.         break;
  1236.     }
  1237. #endif
  1238.     stats.best_line[p].MakeNull();
  1239.     static const Boolean end_of_game[] = { False, False, False, True, True,
  1240.                                True, True, True, True };
  1241.     if (!end_of_game[(int)stats.state] && 
  1242.         global_options->can_resign() && 
  1243.         stats.value <= Constants::Contempt)
  1244.     {
  1245.         // We resign only if behind in material and if our positional
  1246.         // score is low.
  1247.         if (Scoring::positional_score(ABoard) < 40)
  1248.            stats.state = Resigns;
  1249.     }
  1250. #ifdef USE_HASH
  1251.     // This doesn't free memory, just marks it all as available again.
  1252.     hash_table->clear();
  1253. #endif
  1254. #ifdef WINDOWS
  1255.     --num_searches;
  1256. #endif
  1257.     searching = False;
  1258.     return ret_val;
  1259. }
  1260.  
  1261. unsigned Search::hints( const Board &ABoard,
  1262.         Move *moves,
  1263.         unsigned max_moves)
  1264. {
  1265.     searching = True;
  1266.     Search_Limit limit;
  1267.     limit.max_ply = 2;
  1268.     timeCtrl = Time_Control(Fixed_Ply,limit);
  1269.                    
  1270.     side_to_move = ABoard.Side();
  1271.     start_time = time(NULL);
  1272.     num_pos = num_moves = 0L;
  1273. #ifdef NULL_MOVE
  1274.     null_move = False;
  1275. #endif
  1276.     state = Search::Normal;
  1277.     extend = 0;
  1278.     int i;
  1279.     move_stack[0] = NULL;
  1280.     Move_Ordering::clear_killer();
  1281.     ply0moves_generated = False;
  1282.     ply0move_count = 0;
  1283.  
  1284.     Boolean terminate = False;
  1285.     time_up = False; 
  1286.     terminated = False;
  1287.     max_depth = display_depth = 1;
  1288.     plies_done = 0;
  1289.     for (i = 0; i < Constants::MaxPly; i++)
  1290.     {
  1291.     move_stack[i] = NULL;
  1292.     moves_generated[i] = NULL;
  1293.     candidates[i] = NULL;
  1294.         pv[i].MakeNull();
  1295.     }
  1296. #ifdef WINDOWS
  1297.     bkgrnd_search = True;
  1298.     assert(num_searches < MAX_SEARCHES);
  1299.     search_number = num_searches;
  1300.     searches[search_number] = this;
  1301.     ++num_searches;
  1302. #endif
  1303.  
  1304.     int value = evalu8(ABoard);
  1305.     int lo_window, hi_window;
  1306.     lo_window = value - Constants::Initial_Search_Window / 2;
  1307.     hi_window = value + Constants::Initial_Search_Window / 2;
  1308.     Board board_copy = ABoard;
  1309.     value = 
  1310.       move_search(board_copy, lo_window, hi_window, 0, True,
  1311.               terminate, pv);
  1312.     if (!terminate)
  1313.     {
  1314.        if (value > hi_window)
  1315.        {
  1316.          value =
  1317.           move_search(board_copy, hi_window, Constants::BIG-1, 0, True,
  1318.                   terminate, pv);
  1319.        }
  1320.        else if (value < lo_window )
  1321.        {
  1322.         value =
  1323.          move_search(board_copy, -Constants::BIG, lo_window, 0, True,
  1324.                   terminate, pv);
  1325.        }
  1326.     }
  1327.     for (i = 0; i < Constants::MaxPly; i++)
  1328.     {
  1329.     delete move_stack[i];
  1330.     if (moves_generated[i])
  1331.        delete [] moves_generated[i];
  1332.     if (candidates[i])
  1333.        delete [] candidates[i];
  1334.     }
  1335.     // Don't clear the hash table.  Storage for the nodes and lists in the
  1336.     // table may be shared with another search in progress.  When that
  1337.     // search terminates, our memory will be cleaned up, too.
  1338.     Move_Ordering::sort_moves(ply0moves, ply0scores, ply0move_count);
  1339.     int n = Util::Min(ply0move_count,max_moves);
  1340.     for (i = 0; i < n; i++)
  1341.         moves[i] = ply0moves[i];
  1342. #ifdef WINDOWS
  1343.     --num_searches;
  1344. #endif
  1345.     searching = False;
  1346.     return n;
  1347. }
  1348.  
  1349.  
  1350.